package com.hy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:最大化一张图中的路径价值
 * <p>
 * User:Mr.Du
 * Date:2024/7/1
 * Time:11:15
 */
public class MaximalPathQuality {

    /**
     * 最大化一张图中的路径价值
     *
     * @param values 每个节点的价值数组。
     * @param edges 图的边数组，每个元素是一个包含三个整数的数组，表示一条边连接的两个节点和这条边的耗时。
     * @param maxTime 最大允许的总耗时。
     * @return 从根节点到叶子节点的最大路径质量。
     */
    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        // 节点的数量
        int n = values.length;
        // 创建图的邻接表表示
        List<int[]>[] g = new ArrayList[n];
        // 初始化邻接表
        Arrays.setAll(g, i -> new ArrayList<>());
        // 遍历边，构建无向图的邻接表
        for(int[] edge : edges){
            int x = edge[0];
            int y = edge[1];
            int z = edge[2];
            g[x].add(new int[]{y, z});
            g[y].add(new int[]{x, z});
        }
        // 访问标记数组，用于标记节点是否已被访问
        boolean[] vis = new boolean[n];
        // 根节点已访问
        vis[0] = true;
        // 从根节点开始深度优先搜索
        return dfs(0, 0, values[0], vis, g, values, maxTime);
    }


    /**
     * 深度优先搜索函数，用于计算在不超过最大时间限制的情况下，从节点x出发能够获得的最大价值。
     *
     * @param x 当前节点的索引。
     * @param sumTime 当前累计的时间。
     * @param sumValue 当前累计的价值。
     * @param vis 记录节点是否已访问的标记数组。
     * @param g 图的邻接表表示。
     * @param values 每个节点对应的价值数组。
     * @param maxTime 最大时间限制。
     * @return 从当前节点出发，在不超过最大时间限制的情况下，能够获得的最大价值。
     */
    private int dfs(int x, int sumTime, int sumValue, boolean[] vis, List<int[]>[] g, int[] values, int maxTime) {
        // 如果当前节点是目标节点，则返回当前累计的价值，否则返回0
        int res = x == 0 ? sumValue : 0;
        for (int[] e : g[x]) {
            int y = e[0];
            int t = e[1];
            // 如果当前累计时间加上边的时间超过最大时间限制，则跳过当前边
            if (sumTime + t > maxTime) {
                continue;
            }
            // 如果当前节点已访问，则直接递归搜索下一个节点
            if (vis[y]) {
                res = Math.max(res, dfs(y, sumTime + t, sumValue, vis, g, values, maxTime));
            } else {
                // 如果当前节点未访问，则标记为已访问，递归搜索下一个节点，并累加当前节点的价值
                vis[y] = true;
                // 每个节点的价值至多算入价值总和中一次
                res = Math.max(res, dfs(y, sumTime + t, sumValue + values[y], vis, g, values, maxTime));
                // 回溯，撤销当前节点的访问标记
                vis[y] = false; // 恢复现场
            }
        }
        return res;
    }

}
